package tree

//给定一个二叉树，检查它是否是镜像对称的

func isSymmetric(root *Node) bool {
	return check(root, root)
}

//递归法
func check(l, r *Node) bool {
	if l == nil && r == nil {
		return true
	}
	if l == nil || r == nil {
		return false
	}

	return l.Val == r.Val && check(l.Left, r.Right) && check(l.Right, r.Left)
}

//迭代法
func isSymmetricQueue(root *Node) bool {
	u, v := root, root
	q := []*Node{}
	q = append(q, u)
	q = append(q, v)
	for len(q) > 0 {
		u, v = q[0], q[1]
		q = q[2:]
		if u == nil && v == nil {
			continue
		}
		if u == nil || v == nil {
			return false
		}

		if u.Val != v.Val {
			return false
		}
		q = append(q, u.Left)
		q = append(q, v.Right)

		q = append(q, u.Right)
		q = append(q, v.Left)

	}

	return true
}
